package indi.imooc.algorithm.selectionsort;

import indi.imooc.algorithm.sortInterface.SortInterface;
import indi.utils.ArrayGeneratorUtil;
import indi.utils.SortingHelper;

/**
 * 选择排序算法
 */
public class SelectionSort implements SortInterface {
    public SelectionSort(){}

//    public static void sort(int[] e){
//        int temp = 0;
//        for(int i = 0; i < e.length; i++){
//            for(int j = i + 1; j < e.length; j++){
//                if(e[j] < e[i]){
//                    temp = e[j];
//                    e[j] = e[i];
//                    e[i] = temp;
//                }
//            }
//        }
//    }

    public static void sort(int[] e){
        for(int i = 0; i < e.length; i++){
            int minIndex = i;
            for(int j = i + 1; j < e.length; j++){
                if(e[j] < e[minIndex]){
                    minIndex = j;
                }
            }
//            swap(e, i, minIndex);
            int temp = e[i];
            temp = e[minIndex];
            e[minIndex] = e[i];
            e[i] = temp;
        }
    }

    /**
     * 使用带约束的泛型
     * E需要实现Comparable接口
     * 循环不变量arr[i+1,n)未排序,arr[0,i]已排序
     * @param e
     * @param <E>
     */
    @Override
    public <E extends Comparable<E>> void sort(E[] e){
        for(int i = 0; i < e.length; i++){
            int minIndex = i;
            for(int j = i + 1; j < e.length; j++){
                if(e[j].compareTo(e[minIndex]) < 0){
                    minIndex = j;
                }
            }
            swap(e, i, minIndex);
        }
    }

    public static <E> void swap(E[] e, int i, int minIndex) {
        E temp = e[minIndex];
        e[minIndex] = e[i];
        e[i] = temp;
    }


    @Override
    public <E extends Comparable<E>> void  sort2(E[] arr){

    }

    /**
     * 循环不变量arr[i,n)已排序,arr[0,i)未排序
     * @param arr
     * @param <E>
     */
    @Override
    public <E extends Comparable<E>> void sort3(E[] arr) {
        for (int i = arr.length - 1; i >= 0 ; i--) {
            int maxIndex = i;
            for (int j = 0 ; j < i ; j++) {
                if (arr[j].compareTo(arr[maxIndex]) > 0){
                    maxIndex = j;
                }
            }
            swap(arr,i,maxIndex);
        }
    }

    public static <E> void swap2(E[] arr, int i, int maxIndex) {
        E temp = arr[maxIndex];
        arr[maxIndex] = arr[i];
        arr[i] = temp;

    }

    public static void main(String[] args) {

        /**
         * 排序测试v1.0
         */
//        Integer[] arr = {5,5,9,2,4,6};
//        sort(arr);
//        for(int e : arr){
//            System.out.print(e + " ");
//            System.out.println();
//        }

//        Student[] students = {new Student(20,"ali"),new Student(30,"bob"),new Student(40,"candy"),};
//        sort(students);
//        for (Student student : students){
//            System.out.print(student);
//            System.out.println();
//        }


        /**
         * 排序测试v2.0
         */
//        long startTime = System.nanoTime();
//        sort(arr);
//        long endTime = System.nanoTime();
//        System.out.println((int)(endTime - startTime)/1000_000_000.0);
//
//        boolean res = SortingHelper.isSorted(arr);
//        if (!res){
//            throw  new RuntimeException("selectionSort fail");
//        }

        /**
         * 排序测试v3.0
         */
        int[] dataSize = {10000,10_0000};
//        int[] dataSize = {1};
        for (int n : dataSize){
            Integer[] arr = ArrayGeneratorUtil.generateRandomArray(n,n);
            SortingHelper.testSort(SelectionSort.class,"selectionSort",arr);
        }

    }


}
